/**
 * 面试题16：数值的整数次方
 */
public class Offer_16 {
    /**
     * 方法三：快速幂 + 迭代
     */
    public double myPow(double x, int n) {
        // 底数为 0
        if (x == 0) {
            return 0;
        }
        // 指数为 0
        if (n == 0) {
            return 1.0;
        }
        // 指数为 1
        if (n == 1) {
            return x;
        }

        double ans = 1.0;
        // Java 中 int 变量 [−2147483648, 2147483647]，
        // 因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错。
        long N = n;
        if (N < 0) {
            N = -N;
            x = 1.0 / x;
        }
        // 循环计算，当 N == 0 时跳出
        while (N > 0) {
            // 当 (N & 1) == 1 时，将当前 x 乘入 res
            // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
            if ((N & 1) == 1) {
                ans *= x;
            }
            // 执行 x = x^2
            x *= x;
            // 执行 n 右移一位
            N >>= 1;
        }
        return ans;
    }

    /**
     * 方法二：快速幂 + 递归
     */
    public double myPow2(double x, int n) {
        // 底数为 0
        if (x == 0) {
            return 0;
        }
        // 指数为 0
        if (n == 0) {
            return 1.0;
        }
        // 指数为 1
        if (n == 1) {
            return x;
        }

        // Java 中 int 变量 [−2147483648, 2147483647]，
        // 因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错。
        long N = n;
        return N > 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    private double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return (N % 2 == 0) ? (y * y) : (y * y * x);
    }

    /**
     * 方法一：循环（超时）
     */
    public double myPow1(double x, int n) {
        // 底数为 0
        if (x == 0) {
            return 0;
        }
        // 指数为 0
        if (n == 0) {
            return 1.0;
        }
        // 指数为 1
        if (n == 1) {
            return x;
        }

        double ans = 1.0;
        long N = n;
        if (N < 0) {
            N = -N;
            x = 1.0 / x;
        }
        for (long i = 0; i < N; i++) {
            ans *= x;
        }
        return ans;
    }

    public static void main(String[] args) {
        Offer_16 solution = new Offer_16();
        System.out.println(solution.myPow(2.1, 3));
        System.out.println(solution.myPow(2, -2));
    }
}
